package listNodePractice;

public class Class19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1=head;
        int i=0;
        while (p1!=null&&i<n){
            p1=p1.next;
            i++;
        }
        ListNode p2=head;
        //虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next=p2;

//链表只有一个节点的时候
        if (p1==null){
            return p1;
        }
////链表有两个节点的时候
        if (p1.next==null){
//            p2.next=p1.next;
            head.next=null;
            return head;
        }
//p1.next==null的时候刚好到p1刚好指向链表的最后一个节点
        while (p1.next!=null){
            p2=p2.next;
            p1=p1.next;
        }
        p2.next=p1;
        return dummy.next;
    }

    public ListNode removeNthFromEnd1(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
        ListNode x = findFromEnd(dummy, n + 1);
        // 删掉倒数第 n 个节点
        x.next = x.next.next;
        return dummy.next;
    }


    ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 先走 k 步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1 和 p2 同时走 n - k 步
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        // p2 现在指向第 n - k 个节点
        return p2;
    }


    public static void main(String[] args) {



        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        Class19 class19 = new Class19();
        ListNode listNode = class19.removeNthFromEnd(listNode1, 2);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode=listNode.next;
        }

    }



}
